//import javax.print.attribute.standard.Fidelity;
//import java.time.Year;
//import java.util.*;
//
//public class Main {
//
////    public static void main0 (String[] args) {
////        Rectangle[] rectangles = new Rectangle[2];
////        Circle[] circles = new Circle[2];
////        int i = 0;
////        Scanner scanner = new Scanner(System.in);
////        while (i < 2) {
////            int width = scanner.nextInt();
////            int length = scanner.nextInt();
////            Rectangle rectangle = new Rectangle(width, length);
////            rectangles[i] = rectangle;
////            i++;
////        }
////        i = 0;
////        while (i < 2) {
////            int radius = scanner.nextInt();
////            Circle circle = new Circle(radius);
////            circles[i] = circle;
////            i++;
////        }
////        int retPerimeter = rectangles[0].getPerimeter() + rectangles[1].getPerimeter() + circles[0].getPerimeter() + circles[1].getPerimeter();
////        int retArea = circles[0].getArea() + circles[1].getArea() + rectangles[0].getArea() +rectangles[1].getArea();
////        System.out.println(retPerimeter);
////        System.out.println(retArea);
////        System.out.println(Arrays.deepToString(rectangles));
////        System.out.println(Arrays.deepToString(circles));
////    }
//
////    public static void main1(String[] args) {
////        Figure[] figures = new Figure[4];
////        int i = 0;
////        Scanner scanner = new Scanner(System.in);
////        while (i < 2) {
////            int width = scanner.nextInt();
////            int length = scanner.nextInt();
////            Figure figure = new Rectangle(width, length);
////            figures[i] = figure;
////            i++;
////        }
////        while (i < 4) {
////            int radius = scanner.nextInt();
////            Figure figure = new Circle(radius);
////            figures[i] = figure;
////            i++;
////        }
////        int retPerimeter = 0;
////        int retArea = 0;
////        for (int j = 0; j < figures.length; j++) {
////            retPerimeter += figures[j].getPerimeter();
////            retArea += figures[j].getArea();
////        }
////        Rectangle[] rectangles = new Rectangle[2];
////        Circle[] circles = new Circle[2];
////        for (int j = 0; j < 4; j++) {
////            if (j < 2) {
////                rectangles[j] = (Rectangle) figures[j];
////            } else {
////                circles[j - 2] = (Circle) figures[j];
////            }
////        }
////        System.out.println(retPerimeter);
////        System.out.println(retArea);
////        System.out.println(Arrays.deepToString(rectangles));
////        System.out.println(Arrays.deepToString(circles));
////    }
//
//    public static void main2 (String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        Stack<Person> stack = new Stack<>();
//        while (n != 0) {
//            String name = scanner.next();
//            int age = scanner.nextInt();
//            boolean gender = scanner.nextBoolean();
//            Person person = new Person(name, gender, age);
//            stack.push(person);
//            n--;
//        }
//        while (!stack.empty()) {
//            System.out.println(stack.pop().toString());
//        }
//        Person person2 = new Person();
//        System.out.println(person2);
//    }
//
//    public static void main3 (String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        Stack<Person> stack = new Stack<>();
//        while (n != 0) {
//            String name = scanner.next();
//            int age = scanner.nextInt();
//            boolean gender = scanner.nextBoolean();
//            Person person = new Person(name, gender, age);
//            stack.push(person);
//            n--;
//        }
//        while (!stack.empty()) {
//            System.out.println(stack.pop().toString());
//        }
//        Person person2 = new Person();
//        System.out.println(person2);
//    }
//
//    public static void main4 (String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int n = scanner.nextInt();
//        Stack<Person> stack = new Stack<>();
//        while (n != 0) {
//            String name = scanner.next();
//            int age = scanner.nextInt();
//            boolean gender = scanner.nextBoolean();
//            Person person = new Person(name, gender, age);
//            stack.push(person);
//            n--;
//        }
//        while (!stack.empty()) {
//            System.out.println(stack.pop().toString());
//        }
//        Person person2 = new Person();
//        System.out.println(person2);
//    }
//
//    public static void main5(String[] args) {
//        ArrayList<PersonOverride> person1 = new ArrayList<>();
//        ArrayList<PersonOverride> person2 = new ArrayList<>();
//        Scanner scanner = new Scanner(System.in);
//        int n1 = scanner.nextInt();
//        int n2 = scanner.nextInt();
//        while (n1 != 0) {
//            PersonOverride personOverride = new PersonOverride();
//            person1.add(personOverride);
//            n1--;
//        }
//        int i = 0;
//        while (n2 != 0) {
//            String name = scanner.next();
//            int age = scanner.nextInt();
//            boolean gender = scanner.nextBoolean();
//            PersonOverride personOverride = new PersonOverride(name, age, gender);
//            boolean flg = true;
//            if (person2.isEmpty()) {
//                person2.add(personOverride);
//            } else {
//                while (i < person2.size()) {
//                    if (person2.get(i).equals(personOverride)) {
//                        flg = false;
//                        break;
//                    }
//                    i++;
//                }
//                if (flg) {
//                    person2.add(personOverride);
//                }
//            }
//            n2--;
//        }
//        while (person1.size() != n1) {
//            System.out.println(person1.get(n1));
//            n1++;
//        }
//        while (person2.size() != n2) {
//            System.out.println(person2.get(n2));
//            n2++;
//        }
//        System.out.println(person2.size());
//        System.out.println(Arrays.toString(PersonOverride.class.getConstructors()));
//    }
//
//    public static void main6(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        while (scanner.hasNextInt()) {
//            int n = scanner.nextInt();
//            String[] strings = new String[n];
//            int i = 1;
//            while (i <= n) {
////                strings[i - 1] = multiplicationTable(i);
//                i++;
//            }
//            i = 0;
//            while (i < n) {
//                System.out.println(strings[i]);
//                i++;
//            }
//            System.out.println(Arrays.deepToString(strings));
//        }
//    }
//
//    public static void main7 (String[] args) {
//            Scanner scanner = new Scanner(System.in);
//            ArrayList<String> strings = new ArrayList<>();
//            while (scanner.hasNextInt()) {
//                int n = scanner.nextInt();
//                int i = 1;
//                while (i <= n) {
//                    strings.add(multiplicationTable(i));
//                    i++;
//                }
//                i = 0;
//                while (i < n) {
//                    String s = strings.get(i);
//                    System.out.println(s);
//                    i++;
//                }
//                System.out.printf(String.valueOf(strings));
//                System.out.println();
//                strings.clear();
//            }
//
//    }
//
//    public static void main8(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        int[] nums = new int[]{};
//        while (scanner.hasNextLine()) {
//            String choice = scanner.nextLine();
//            if (choice.equals("fib")) {
//                int n = scanner.nextInt();
//                fibAll(n);
//            } else if (choice.equals("sort")) {
//                nums = sort();
//                //sort()有nextLine 防止重复吃回车
//                continue;
//            } else if (choice.equals("search")) {
//                System.out.println(search(nums, scanner.nextInt()));
//            } else if (choice.equals("getBirthDate")) {
//                int n = scanner.nextInt();
//                //吃回车
//                scanner.nextLine();
//                while (n != 0) {
//                    getBirthDate(scanner.nextLine());
//                    n--;
//                }
//                //原因同上
//                continue;
//            } else {
//                System.out.println("exit");
//                return;
//            }
//            //非常重要!!用来吃掉回车 防止下一次的nextLine直接读取回车导致程序执行
//            scanner.nextLine();
//        }
//    }
//
//    public static void main9(String[] args) {
//        Scanner in = new Scanner(System.in);
//        int n = in.nextInt();
//        int m = in.nextInt();
//        int k = in.nextInt();
//        Random random = new Random(k);
//        int ret = 0;
//        for (int i = 0; i < n; i++) {
//            ret = random.nextInt(m - 1);
//        }
//        System.out.println(ret);
//    }
//    public static void main10(String[] args){
//        int n=0;
//        Scanner in = new Scanner(System.in);
//        String[] num = in.nextLine().split(" ");
//        int[] nums = new int[3];
//        for (int i = 0; i < 3; i++) {
//            nums[i] = Integer.parseInt(num[i]);
//        }
//        Random random = new Random(nums[2]);
//        for(int i = 0; i < nums[0];i++){
//            n = random.nextInt(nums[1] - 1);
//        }
//        System.out.print(n);
//    }
//
//    public static void fibAll (int n) {
//        int i = 1;
//        while (i < n) {
//            System.out.print(fib(i++) + " ");
//        }
//        System.out.println(fib(i));
//    }
//
//    public static int fib (int n) {
//        if (n <= 1) {
//            return n;
//        } else {
//            return fib (n - 1) + fib(n - 2);
//        }
//    }
//
//    public static int[] sort () {
//        Scanner scanner = new Scanner(System.in);
//        String s = scanner.nextLine();
//        String[] strings = s.split(" ");
//        int[] ret = new int[strings.length];
//        int i = 0;
//        while (i < strings.length) {
//            ret[i] = Integer.parseInt(strings[i]);
//            i++;
//        }
//        Arrays.sort(ret);
//        System.out.println(Arrays.toString(ret));
//        return Arrays.copyOf(ret, ret.length);
//    }
//
//    public static int search (int[] nums, int n) {
//        HashSet<Integer> hashSet = new HashSet<>();
//        for (int i = 0; i < nums.length; i++) {
//            hashSet.add(nums[i]);
//        }
//        if (hashSet.contains(n)) {
//            return Arrays.binarySearch(nums, n);
//        } else {
//            return -1;
//        }
//    }
//
//    public static void getBirthDate (String id) {
//        StringBuilder stringBuilder = new StringBuilder();
//        int i = 6;
//        while (i < 14) {
//            if (i == 10 || i == 12) {
//                stringBuilder.append("-");
//            }
//            stringBuilder.append(id.charAt(i));
//            i++;
//        }
//        System.out.println(stringBuilder);
//    }
//
//    public static String multiplicationTable(int n) {
//        int i = 1;
//        StringBuilder stringBuilder = new StringBuilder();
//        while (i < n) {
//            stringBuilder.append(n + "*" + i + "=" + n*i + "  ");
//            i++;
//        }
//        stringBuilder.append(n + "*" + i + "=" + n*i);
//        return stringBuilder.toString();
//    }
//
////    public static void main(String[] args) {
////        Scanner input = new Scanner(System.in);
////        int year = 0;
////        int month = 0;
////        int day = 0;
////
////        int choice = input.nextInt();
////
////        if (choice == 1) { // test getNextNDays method
////            int m = 0;
////            year = Integer.parseInt(input.next());
////            month = Integer.parseInt(input.next());
////            day = Integer.parseInt(input.next());
////
////            DateUtil date = new DateUtil(year, month, day);
////
////            if (!date.checkInputValidity()) {
////                System.out.println("Wrong Format");
////                System.exit(0);
////            }
////
////            m = input.nextInt();
////
////            if (m < 0) {
////                System.out.println("Wrong Format");
////                System.exit(0);
////            }
////
////            System.out.print(date.getYear() + "-" + date.getMonth() + "-" + date.getDay() + " next " + m + " days is:");
////            System.out.println(date.getNextNDays(m).showDate());
////        } else if (choice == 2) { // test getPreviousNDays method
////            int n = 0;
////            year = Integer.parseInt(input.next());
////            month = Integer.parseInt(input.next());
////            day = Integer.parseInt(input.next());
////
////            DateUtil date = new DateUtil(year, month, day);
////
////            if (!date.checkInputValidity()) {
////                System.out.println("Wrong Format");
////                System.exit(0);
////            }
////
////            n = input.nextInt();
////
////            if (n < 0) {
////                System.out.println("Wrong Format");
////                System.exit(0);
////            }
////
////            System.out.print(
////                    date.getYear() + "-" + date.getMonth() + "-" + date.getDay() + " previous " + n + " days is:");
////            System.out.println(date.getPreviousNDays(n).showDate());
////        } else if (choice == 3) {    //test getDaysofDates method
////            year = Integer.parseInt(input.next());
////            month = Integer.parseInt(input.next());
////            day = Integer.parseInt(input.next());
////
////            int anotherYear = Integer.parseInt(input.next());
////            int anotherMonth = Integer.parseInt(input.next());
////            int anotherDay = Integer.parseInt(input.next());
////
////            DateUtil fromDate = new DateUtil(year, month, day);
////            DateUtil toDate = new DateUtil(anotherYear, anotherMonth, anotherDay);
////
////            if (fromDate.checkInputValidity() && toDate.checkInputValidity()) {
////                System.out.println("The days between " + fromDate.showDate() +
////                        " and " + toDate.showDate() + " are:"
////                        + fromDate.getDaysofDates(toDate));
////            } else {
////                System.out.println("Wrong Format");
////                System.exit(0);
////            }
////        }
////        else{
////            System.out.println("Wrong Format");
////            System.exit(0);
////        }
////    }
//}
//
//class DateUtil {
//    private int year;
//    private int month;
//    private int day;
//
//    public DateUtil(int year, int month, int day) {
//        this.year = year;
//        this.month = month;
//        this.day = day;
//    }
//
//    public DateUtil() {}
//
//    public int getYear() {
//        return year;
//    }
//
//    public void setYear(int year) {
//        this.year = year;
//    }
//
//    public int getMonth() {
//        return month;
//    }
//
//    public void setMonth(int month) {
//        this.month = month;
//    }
//
//    public int getDay() {
//        return day;
//    }
//
//    public void setDay(int day) {
//        this.day = day;
//    }
//
//    //检测输入的年、月、日是否合法
//    public boolean checkInputValidity() {
//        if (this.day >= 1 && this.day <= 31) {
//            if (this.month >= 1 && this.month < 12) {
//                if (this.year >= 1820 && this.year <= 2020) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    //判断year是否为闰年
//    public boolean isLeapYear(int year) {
//        if (this.year % 4 != 0) {
//            return false;
//        } else {
//            //世纪闰年:加一个%400的判断
//            if (this.year % 100 == 0) {
//                if (this.year % 400 == 0) {
//                    return true;
//                } else {
//                    return false;
//                }
//            }
//            //非世纪闰年
//             else {
//                return true;
//            }
//        }
//    }
//
//    //比较当前日期与date的大小（先后）
//    public boolean compareDates(DateUtil date) {
//        if (date.year < this.year) {
//            return false;
//        } else if (date.year > this.year) {
//            return true;
//        } else {
//            if (date.month < this.year) {
//                return false;
//            } else if (date.month > this.month) {
//                return true;
//            } else {
//                if (date.day <= this.day) {
//                    return false;
//                } else {
//                    return true;
//                }
//            }
//        }
//    }
//
//    //判断两个日期是否相等
//    public boolean equalTwoDates(DateUtil date) {
//        if (date.year == this.year) {
//            if (date.month == this.month) {
//                if (date.day == this.day) {
//                    return true;
//                }
//            }
//        }
//        return false;
//    }
//
//    //求当前日期与date之间相差的天数
//
//
//    public int getMonthofDays (int mon) {
//        if (mon < 8) {
//            if (mon % 2 == 0) {
//                if (mon != 2) {
//                    return 30;
//                } else {
//                    if (isLeapYear(this.year)) {
//                        return 29;
//                    } else {
//                        return 30;
//                    }
//                }
//            } else {
//                return 31;
//            }
//        } else {
//            if (mon % 2 == 0) {
//                return 31;
//            } else {
//                return 30;
//            }
//        }
//    }
//
//
//    //以“year-month-day”格式返回日期值
//    public String showDate() {
//        return this.year + "-" + this.month + "-" + this.day;
//    }
//}
//
//
//class PersonOverride {
//    private String name;
//    private int age;
//    private boolean gender;
//
//    public PersonOverride () {
//        this("default", 1, true);
//    }
//
//    public PersonOverride (String name, int age, boolean gender) {
//        this.name = name;
//        this.age = age;
//        this.gender = gender;
//    }
//
//    @Override
//    public String toString () {
//        return name +
//                "-" + age +
//                "-" + gender;
//    }
//
////    public boolean equals (PersonOverride personOverride) {
////        if (personOverride.gender == this.gender) {
////            if (personOverride.name.equals(this.name)) {
////                if (personOverride.age == this.age) {
////                    return true;
////                }
////            }
////        }
////        return false;
////    }
//
//    public boolean equals(Object obj) {
//        if (obj == this) {
//            return true;
//        }
//        if (obj == null) {
////            throw new NullPointerException();
//            return false;
//        }
//        if (obj instanceof PersonOverride) {
//            PersonOverride person = (PersonOverride) obj;
//            if (person.name.equals(this.name)
//                    && person.age == this.age
//                    && person.gender == this.gender) {
//                return true;
//            }
//        }
//        return false;
//    }
//}
//
////abstract class Figure {
////    public Figure () {}
////
////    public Figure (int width, int length) {
////        this.length = length;
////        this.width = width;
////    }
////
////    public Figure (int radius) {
////        this.radius = radius;
////    }
////
////
////    int width;
////    int length;
////    int radius;
////
////
////    public abstract int getArea ();
////
////    public abstract int getPerimeter ();
////
////}
////
////class Circle extends Figure{
////    public Circle () {
////
////    }
////
////    public Circle (int radius) {
////        super(radius);
////        this.radius = radius;
////    }
////
////
////    @Override
////    public int getArea () {
////        return (int) (Math.PI * this.radius * this.radius);
////    }
////
////    @Override
////    public int getPerimeter() {
////        return (int) (Math.PI * 2 * radius);
////    }
////
////    @Override
////    public String toString() {
////        return "Circle [" +
////                "radius=" + radius +
////                ']';
////    }
////}
////
////class Rectangle extends Figure {
////
////    public Rectangle (int width, int length) {
////        super(width, length);
////    }
////
////    public Rectangle () {}
////
////    @Override
////    public int getArea() {
////        return super.width * super.length;
////    }
////
////    @Override
////    public int getPerimeter () {
////        return 2 * (this.width + this.length);
////    }
////
////    @Override
////    public String toString() {
////        return "Rectangle [" +
////                "width=" + width +
////                ", length=" + length +
////                ']';
////    }
////}
//
//class Person {
//    private String name;
//    private boolean gender;
//    private int age;
//    private static int idCount;
//    private int id;
//
//    public Person() {
//        System.out.println("This is constructor");
//        System.out.println(this.name + "," + this.age + "," + this.gender + "," + this.id);
//    }
//
//    public Person (String name, boolean gender, int age) {
//        this.name = name;
//        this.gender = gender;
//        this.age = age;
//    }
//
//    {
//        idCount++;
//        id = idCount - 1;
//        System.out.println("This is initialization block, id is " + id);
//    }
//
//    static {
//        System.out.println("This is static initialization block");
//    }
//
//    @Override
//    public String toString () {
//        return "Person [name=" + this.name + ", age=" + this.age + ", gender=" + this.gender + ", id=" + id + "]";
//    }
//}
//
////public class Main {
////    public static void main (String[] args) {
////        Scanner scanner = new Scanner(System.in);
////        int n = scanner.nextInt();
////        Stack<Person> stack = new Stack<>();
////        while (n != 0) {
////            String name = scanner.next();
////            int age = scanner.nextInt();
////            boolean gender = scanner.nextBoolean();
////            Person person = new Person(name, age, gender);
////            stack.push(person);
////            n--;
////        }
////        while (!stack.empty()) {
////            System.out.println(stack.pop().toString());
////        }
////        Person person2 = new Person();
////        System.out.println(person2);
////    }
////}
////class Person {
////    private String name;
////    private int age;
////    private boolean gender;
////    private int id;
////
////    public Person() {
////        System.out.println("This is constructor");
////        System.out.println(this.name + "," + this.age + "," + this.gender + "," + this.id);
////    }
////
////    public Person (String name, int age, boolean gender) {
////        this.name = name;
////        this.age = age;
////        this.gender = gender;
////    }
////
////    @Override
////    public String toString () {
////        return "Person [name=" + this.name + ", age=" + this.age + ", gender=" + this.gender + ", id=" + this.id + "]";
////    }
////
////    public String getName () {
////        return this.name;
////    }
////
////    public void setName (String name) {
////        this.name = name;
////    }
////
////    public int getAge () {
////        return this.age;
////    }
////
////    public void setAge (int age) {
////        this.age = age;
////    }
////
////    public boolean getGender () {
////        return this.gender;
////    }
////
////    public void setGender (boolean gender) {
////        this.gender = gender;
////    }
////
////    public int getId () {
////        return this.id;
////    }
////
////    public void setId (int id){
////        this.id = id;
////    }
////}